﻿//https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

//暴力求解
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		int n = nums.size();
		for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数
			for (int j = i + 1; j < n; j++) { // 第⼆层循环从 i 位置之后列举第⼆个数
				if (nums[i] + nums[j] == target) // 两个数的和等于⽬标值，说明我们已经找到结果了
					return { nums[i], nums[j] };
			}
		}
		return { -1, -1 };
	}
};

//我的
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		int left = 0, right = 1;
		//找到右指针
		for (; right < nums.size(); ++right)
		{
			if (nums[right] > target)break;
		}

		//右指针 = nums.size()
		right--;
		while (left < right && right < nums.size() && nums[right] + nums[left] != target)
		{
			if (nums[right] + nums[left] < target)left++;
			else if (nums[right] + nums[left] > target)right--;
		}

		return { nums[left],nums[right] };
	}
};
//答案
class Solution
{
public:
	vector<int> twoSum(vector<int>& nums, int target)
	{
		int left = 0, right = nums.size() - 1;
		while (left < right)
		{
			int sum = nums[left] + nums[right];
			if (sum > target) right--;
			else if (sum < target) left++;
			else return { nums[left], nums[right] };
		}
		
		return { -4941, -1 };
	}
};